package xin.yangshuai.leetcode01.question41;

//给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
//请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
//
//
//
//示例 1：
//
//输入：nums = [1,2,0]
//输出：3
//解释：范围 [1,2] 中的数字都在数组中。
//
//示例 2：
//
//输入：nums = [3,4,-1,1]
//输出：2
//解释：1 在数组中，但 2 没有。
//
//示例 3：
//
//输入：nums = [7,8,9,11,12]
//输出：1
//解释：最小的正数 1 没有出现。
//
//
//
//提示：
//
//    1 <= nums.length <= 105
//    -231 <= nums[i] <= 231 - 1

import java.util.HashSet;
import java.util.Set;

public class Question41 {

    public static void main(String[] args) {
        Question41.Solution solution = new Question41().new Solution();

        int[] nums = {1, 2, 0};

        int i = solution.firstMissingPositive(nums);
        System.out.println(i);
    }


    class Solution {
        public int firstMissingPositive(int[] nums) {

            Set<Integer> set = new HashSet<>();

            int target = 1;
            int next = 0;
            for (int num : nums) {

                next = next > num + 1 ? next : num + 1;

                if (num > target) {
                    set.add(num);
                } else if (num == target) {
                    boolean flag = true;
                    for (int i = 0; i < set.size(); i++) {
                        target++;
                        if (!set.contains(target)) {
                            flag = false;
                            break;
                        }
                    }
                    if (flag) {
                        target = next;
                    }
                }
            }
            return target;
        }
    }
}
